﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
//using Simulated_Annealing.VRP;

namespace Simulated_Annealing
{
    class Neighborhood
    {

        public static int[,] routepairlist(VRP s_current, Random random) //this function is called from program.cs, and it generates the array of route pairs 
        {

            s_current.route_clean(s_current);
            int numberofroutes = s_current.routes.Count;
            int numpairs = ((numberofroutes) * (numberofroutes) - (numberofroutes)) / 2;
            int[,] routepairsij = new int[numpairs, 2];   //the matrix that will hold all possible unique route pairs
            int row = -1;
            for (int i = 0; i < numberofroutes; i++)
            {
                for (int j = i + 1; j < numberofroutes; j++)
                {
                    row = row + 1;
                    routepairsij[row,0]= i;
                    routepairsij[row, 1] = j;
                }
            }

            
            int[,] routepairlistsorted = new int[numpairs, 2];
          
            
            int k = 0;

            List<List<int>> routepair_temp =new List<List<int>>();
            
            for (int i=0; i<routepairsij.GetLength(0);i++)
            {
                int [,] temp=new int[1,2];
                temp[0,0]= routepairsij[i,0];
                temp[0,1]= routepairsij[i,1];
                routepair_temp.Add(temp.OfType<int>().ToList());
            }

            while (routepair_temp.Count > 0)
            {
                int index = random.Next(0,routepair_temp.Count);
                routepairlistsorted[k, 0] = routepair_temp[index][0];
                routepairlistsorted[k, 1] = routepair_temp[index][1];
                routepair_temp.RemoveAt(index);
                k++;
            }

            return routepairlistsorted; 
        }

        public static List<int> randomroute(int routepairindex, int[,] routepairsij, VRP network) // picks the random route from the route pair, and the calls all nodes on that route, and returns the chosen route from the pair
        {
           
            //try to pick the route with the greatest excess capacity as the "route for insert" and the other will be "route for remove" 
            //try to look for a route with a single node on it, and chose that as route to remove
            
            int routeforremove; 
            int routeforinsert;
            Random rnd = new Random();
            int r = rnd.Next(0, 2); //returns either a 0 or a 1
            routeforremove = routepairsij[routepairindex, r];//updated the routeforremove to be the index of the route where we will remove the node
            routeforinsert = routepairsij[routepairindex, 1 - r];

            //if (network.routes[routepairsij[routepairindex, 0]].Count == 1)
            //{
            //    routeforremove = routepairsij[routepairindex, 0];
            //    routeforinsert = routepairsij[routepairindex, 1];
            //}
            //else if (network.routes[routepairsij[routepairindex, 1]].Count == 1)
            //{
            //    routeforremove = routepairsij[routepairindex, 1];
            //    routeforinsert = routepairsij[routepairindex, 0];
            //}
            //else
            //{
            //    Random rnd = new Random();
            //    int r = rnd.Next(0, 2); //returns either a 0 or a 1
            //    routeforremove = routepairsij[routepairindex, r];//updated the routeforremove to be the index of the route where we will remove the node
            //    routeforinsert = routepairsij[routepairindex, 1 - r];
            //} 

            List<int> chosenroutes = new List<int>(); 
            chosenroutes.Add(routeforremove); //the first element of the list will be the route to remove the node
            chosenroutes.Add(routeforinsert); //the second element in the list will be the route to insert the node           
            return chosenroutes; 
        }
        

        public static double insert_cost(List<int> route, int node, int index,VRP network) // here we return the value when you insert a node to a route, if remove, we just delete this value
        {
            network.route_clean(network);
            double oldcost = network.routelength(route,network); //this returns the length of the input route
            double cost = 0;
            //here we need to careful about the insert position, since our route list does not contain the depot

            if(index==0)// if we insert the node as the first node
            {
               
                if (route.Count > 1)
                {
                    cost = network.costmatrix[0][node] + network.costmatrix[node][route[1]] - network.costmatrix[0][route[1]];
                }
                else 
                {
                    cost = network.costmatrix[0][ node] + network.costmatrix[node][route[0]] - network.costmatrix[0][route[0]];
                }


            }
            else if(index==route.Count)   // if we insert the node as the last node
            {
                if (route.Count > 1)
                {
                    cost = network.costmatrix[0][node] + network.costmatrix[node][route[index-1]] - network.costmatrix[0][route[index-1]];
                }
                else  // there is only one node on the routes
                {
                    cost = network.costmatrix[0][node] + network.costmatrix[node][route[0]] - network.costmatrix[0][route[0]];
                }
            }
            else        // if we insert the node in between 
            {
                cost = network.costmatrix[route[index-1]][ node] + network.costmatrix[route[index ]][node] - network.costmatrix[route[index-1]][ route[index]];
            }
            return cost;
        }

        public static double remove_cost(List<int> route, int node, VRP network) // here we return the value when you insert a node to a route, if remove, we just delete this value
        {
            network.route_clean(network);
            double oldcost = network.routelength(route,network); //this returns the length of the input route
            double cost = 0;
            //here we need to careful about the insert position, since our route list does not contain the depot
            int index = route.IndexOf(node);
            if (index == 0)// if we insert the node as the first node
            {
                if (route.Count > 1)
                {
                    cost = network.costmatrix[0][node] + network.costmatrix[node][route[1]] - network.costmatrix[0][route[1]];
                }
                else
                {
                    cost = network.costmatrix[0][node] + network.costmatrix[node][route[0]] - network.costmatrix[0][route[0]];
                }
              
            }
            else if (index == route.Count-1)   // if we insert the node as the last node
            {
                if (route.Count > 1)
                {
                    cost = network.costmatrix[0][node] + network.costmatrix[node][route[route.Count - 2]] - network.costmatrix[0][route[route.Count - 2]];
                }
                else 
                {
                    cost = network.costmatrix[0][node] + network.costmatrix[node][route[0]] - network.costmatrix[0][route[0]];
                }
            }
            else        // if we insert the node in between 
            {
                cost = network.costmatrix[route[index - 1]][node] + network.costmatrix[route[index + 1]][node] - network.costmatrix[route[index - 1]][route[index + 1]];
            }
            return cost;
        }

        public static int best_insert_index(List<int> route, int node,VRP network) // this function will return the optimal insert position, which will use the previous function
        {
            double cost = 0;
            double opt = insert_cost(route,node,0,network); //initialize the opt value
            int index = 0;
            for (int i = 0; i <= route.Count; i++)
            {
                cost = insert_cost(route, node, i,network);
                if (cost <= opt)  //only update the value when there is improvement
                {
                    opt = cost;
                    index = i;
                }

            }
            return index;
        }

        public static int best_remove_node(List<int> route,VRP network) // this function will return optimal position of remove one node from the current route
        {
            double cost = 0;
            double opt = remove_cost(route, route[0], network);
            int index = 0;
            for (int i = 0; i < route.Count; i++)
            {
                cost = remove_cost(route, route[i],network);
                if (cost >= opt)  //only update the value when there is improvement
                {
                    opt = cost;
                    index = i;
                }

            }
            return route[index];
        }

        public static double best_move_cost(VRP neighbor_can, int route_remove_num, int route_insert_num) // this function return the cost of the move
        {
            //VRP neighbor_new = new VRP(neighbor_can);
            //neighbor_new.route_clean();
            neighbor_can.route_clean(neighbor_can);
            int node_inset_index;
            int node;          // the node to remove
            double re_cost;     // remove cost
            double in_cost;     // insert cost
            List<int> route_remove = neighbor_can.routes[route_remove_num];
            List<int> route_inset = neighbor_can.routes[route_insert_num];

            node = best_remove_node(route_remove,neighbor_can);
            re_cost = remove_cost(route_remove, node,neighbor_can);
            node_inset_index = best_insert_index(route_inset, node,neighbor_can);
            in_cost = insert_cost(route_inset, node, node_inset_index,neighbor_can);
            return  in_cost-re_cost;                               // 
        }
        
        public static VRP best_move(VRP neighbor_can, int route_remove_num, int route_insert_num, List<Nodes> nodes)
        {
            VRP neighbor = new VRP(neighbor_can);
            neighbor.route_clean(neighbor);
            double cost_r = 0;
            double cost_i = 0;
            double cost=0;
            double best_cost = neighbor.totalcost(neighbor.routes, neighbor);
            List<int> route_remove = neighbor.routes[route_remove_num];
            List<int> route_insert = neighbor.routes[route_insert_num];
            int best_node_remove = 0;
            int best_insert_position=0;
            int counter = 0;
            for (int i = 0; i < route_remove.Count; i++)
            {
                cost_r = remove_cost(route_remove, route_remove[i], neighbor);
                    int node_remove=route_remove[i];
                    if (node_remove == 0)
                    {
                        Console.Write("REMOVE ZERO NODE");
                        Console.Write(route_remove.ToString());

                        neighbor.routes[route_remove_num].Remove(0);
                        neighbor_can.routes[route_remove_num].Remove(0);
                        return neighbor_can;
                    }

                    int insert_position = best_insert_index(route_insert, node_remove, neighbor);
                    cost_i = insert_cost(route_insert, node_remove, insert_position, neighbor);
                    cost=cost_i-cost_r;
                    if (neighbor.routecapacity(route_insert, neighbor) + neighbor.demandarray[node_remove] <= neighbor.capacity)//check the feasibility
                    {
                        if (cost <= best_cost)
                        {
                            best_cost = cost;
                            best_node_remove = node_remove;
                            best_insert_position = insert_position;

                        }
                        else
                        { continue; }
                    }
                    else
                    {
                        counter++;
                        continue;
                    }
            }

            if (best_node_remove == 0)
            {

                return neighbor_can;

            }
            else
            {
               
                    if (neighbor.routecapacity(route_insert, neighbor) + neighbor.demandarray[best_node_remove] <= neighbor.capacity)
                    {
                        neighbor.routes[route_remove_num].Remove(best_node_remove);
                        neighbor.routes[route_insert_num].Insert(best_insert_position, best_node_remove);
                        return neighbor;
                    }
                    else 
                    {
                        return neighbor_can;
                    }

            }

        }
        public static VRP Create_Neighborhood(VRP s_current, int routepairindex, int[,] routepairsij, List<Nodes> nodes)// this function will return an neighborhood solution if we choose to make the change
        {
           
            //first, we will call randomroute to pick, of the two routes, which on will be assigned to "remove node" and which one will be assigned to "insert node"
            List<int> chosenroutes = new List<int>();
            s_current.route_clean(s_current);
            chosenroutes = randomroute(routepairindex, routepairsij, s_current); // list, where the first # is the route from which we will remove the node, and the second # is the route from which we will insert the node           
            //last, we will call best_move to pick the best node to move between the remove and insert route, and return the neighborhood VRP object
            //in best move, if it's a feasible move, s_neighborhood will "update", otherwise, s_neighborhood will remain the same
           VRP s_neighborhood = new VRP(best_move(s_current, chosenroutes[0], chosenroutes[1], nodes));
           return s_neighborhood;            
        }

    }
}
